2012년도 운영체제 2학기 텀 프로젝트 2

<버퍼 캐쉬 구현>

버퍼 캐쉬의 정의
커널은 모든 파일을 직접 디스크에서 읽고 쓸 수 있으나, 디스크의 느린 데이터 전송 송고 때문에 시스템의 응답시간과 처리능력이 나빠진다. 따라서 커널은 최근 사용된 디스크 블록의 데이터를 유지하는 공통의 내부 데이터 버퍼(이것을 버퍼 캐쉬라 한다)를 관리하여 디스크 액세스를 최소화한다. 커널의 버퍼 캐쉬 모듈은 파일 서브시스템과 블록단위의 장치 드라이버 사이에 위치하고 있다.
커널이 디스크에서 데이터를 읽으려 할 때 우선 버퍼캐쉬에서 읽으려고 시도하고, 만일 데이터가 캐쉬 속에 있으면 그대로 읽게 되고, 없을 경우 커널은 디스크에서 데이터를 읽어 될 수 있는 대로 유익한 데이터를 보관하려는 알고리즘에 따라 캐쉬에 저장한다. 디스크에 쓰려고 하는 데이터의 경우도 나중에 커널이 그것을 이용할 경우를 대비하여 캐쉬에 저장해 둔다.

목적
커널이 어떻게 버퍼 캐쉬를 관리하고 접근하는지 제시된 구현 시나리오(XI번 항목 참조)를 구현하여 버퍼 캐쉬에 대한 내용을 이해하고 숙지한다.

버퍼 할당 알고리즘
다음은 버퍼 할당 알고리즘인 getblk 알고리즘이다.
- 입력 : 파일 시스템 번호, 블록 번호
- 출력 : 블록에 사용할 수 있는 락된(locked) 버퍼
while (버퍼를 찾지 못한다)
{
if (블록이 해쉬대기행렬에 있다)
{

if (버퍼를 사용 중)  // 시나리오 5
{

sleep (해당 버퍼가 빌 때까지);

continue;     // while 루프로 돌아간다.

}

버퍼에 사용중이라는 표시를 한다.   // 시나리오 1

프리 리스트에서 버퍼를 삭제한다.;

return (버퍼);

}

else   // 블록이 해쉬대기행렬에 없다

{

if (프리 리스트상에 버퍼가 없다)  // 시나리오 4

sleep (어떠한 버퍼가 빌 때까지);

continue;  // while 루프로 돌아간다.

}

자유리스트에서 버퍼를 지운다.;

if (버퍼에 delayed write의 표시가 붙어있다)  // 시나리오 3

{

디스크의 버퍼의 내용을 비동기로 출력한다.;

continue;  // while 루프로 돌아간다.

}

// 시나리오 2 - 빈 버퍼의 검출

옛날 해쉬대기 행렬에서 버퍼를 삭제한다.;

새로운 해쉬대기 행렬에 버퍼를 삽입한다.;

return (버퍼);

}

}

}

버퍼 반환 알고리즘
다음은 버퍼 반환 알고리즘인 brelse 알고리즘이다.
- 입력 : 락된(locked) 버퍼
- 출력 : 없음
{

어떤 버퍼가 비기를 기다리던 모든 프로세스를 깨운다.;

이 버퍼가 비기를 기다리던 모든 프로세스를 깨운다;

인터럽트를 막기 위하여 프로세서의 실행레벨을 올린다;

if (버퍼의 내용이 유효이며 버퍼가 오래된 것이 아니다)

버퍼를 프리 리스트의 맨 뒤에 넣는다.;

else

버퍼를 프리 리스트의 맨 앞에 넣는다.;

인터럽트를 허가하기 위하여 프로세서의 실행레벨을 낮춘다;

unlock(버퍼);
}

버퍼헤드의 구조

버퍼는 실제 데이터 영역과 버퍼 헤더로 구성되어 있다.

장치 번호와 블록 번호로 고유한 버퍼를 식별한다.

버퍼 헤드의 자료구조는 다음과 같다.

struct Buffer{

int deviceNum;             // 장치번호

int blkno;	// 블록번호

char* data;	// 데이터 영역의 포인터

int stateFree;	// 버퍼 상태

int stateBusy;	// 버퍼 상태

int stateDelay;	// 버퍼 상태

int stateWrite;	// 버퍼 상태

Buffer* queuePrev;	// 해쉬큐의 다음 버퍼 포인터

Buffer* queueNext;	// 해쉬큐의 앞 버퍼 포인터

Buffer* freeListPrev;      // 프리리스트의 앞 버퍼 포인터

Buffer* freeListNext;      // 프리리스트의 다음 버퍼 포인터

};

해쉬큐의 버퍼 자료구조는 다음과 같다.

class CQueue{

public:

CQueue();

~CQueue();

void makeEmpty();       // 큐를 모두 삭제

bool isEmpty();	// 큐가 비었나 확인

bool isFull();	// 큐가 가득 찼나 확인

void enqueue(Buffer* newbuf);  // 큐의 블록 삽입

void dequeue();	// 큐의 블록 삭제

Buffer* getFront();	// 큐의 첫 블록 리턴

private:

Buffer* front;

};

프리 리스트의 자료 구조는 다음과 같다.

class FreeList{

public:

FreeList(void);

~FreeList(void);

void makeEmpty();	// 리스트를 모두 삭제

bool isEmpty();	// 리스트가 비었나 확인

bool isFull();	// 리스트가 가득 찼나 확인

int getLength();	// 리스트의 길이 리턴

Buffer* getHead();	// 리스트의 헤드 리턴

void insert(Buffer* newBuffer);  // 리스트 추가

void delete(int delNum);         // 리스트 삭제

private:

Buffer* head;

int length;

};

버퍼의 프리 리스트

커널은 LRU(Least Recently Used) 알고리즘에 의해 버퍼들을 연결한 프리 리스트를 보관한다.

프리 리스트는 앞부분에서 버퍼를 취하고 리스트에서 제거 후 사용한 버퍼는 끝에 삽입한다.

프리 리스트는 이중 링크드 원형 리스트로 구성된다.

해쉬큐의 버퍼

버퍼의 장치번호와 블록번호를 해슁하여 별도의 큐로 구성되어 있다.

버퍼를 가져오는 5가지 시나리오

커널이 해쉬큐에서 그 블록을 찾아내고 해당 버퍼는 미사용 중이다.

커널이 해쉬큐에서 그 블록을 찾을 수가 없어 프리 리스트에서 버퍼를 할당한다.

커널이 해쉬큐에서 그 블록을 찾을 수 없어 프리 리스트에서 버퍼를(시나리오 2와 같이) 할당하려고 한다. 그러나 그 버퍼가 “지연쓰기”라고 표시되어 있음을 알게 된다. 이 경우 커널은 그 “지연쓰기” 버퍼를 디스크에 저장해야 하고 다른 버퍼를 할당해야 한다.

커널은 해쉬큐에서 그 블록을 찾을 수 없고 프리버퍼가 없다.

커널이 해쉬큐에서 그 블록을 찾는다. 그러나, 그 버퍼를 누군가 현재 액세스하고 있다.

구현 시나리오

다음과 같은 가상의 하드 디스크 드라이브(virtual HDD) 영역을 할당한다. 이때 할당하는 크기는 구조체 BLK의 배열이며, 크기는 1000이다.

#define SIZE 10000
class VirtualHDD{
public:
VirtualHDD();
~VirtualHDD();
int searchFile(char* fileName);// vHDD에서 파일을 검색
int deleteFile(char* fileName);// vHDD에서 파일을 삭제
int createFile(char* fileName);// vHDD에서 파일을 생성
BLK returnBlk(int blkNum);	// blkNum의 블록 정보를 리턴

private:
BLK vHDD[SIZE];	// 가상의 하드 디스크 드라이브
int file[5000];	// vHDD에서 각 파일의 시작 지점을 저장
};

구조체 BLK는 다음과 같은 데이터를 가진다.
struct BLK{
char* fileName;	// 파일의 이름
int nextBlk;	// 다음 블록을 가리키는 포인터
int prevBlk;	// 이전 블록을 가리키는 포인터
int blkCnt;	// 한 파일에서 순차적으로 할당 받는 번호(출력 시 확인용)
}

BLK는 하드 디스크의 가상의 한 블록을 가리키는 구조체이며, 이 크기는 임의로 4kb라고 가정한다.
즉, 사용자가 12kb 크기의 파일을 입력할 경우, BLK 배열에 있는 원소들이 3개 할당 되어야 한다.

사용자 인터페이스를 만든다. 인터페이스의 항목과 각 동작은 다음과 같다.

사용자 인터페이스와 별개로 가상의 파일을 처리하며, 버퍼 캐시의 현 상황을 실시간을 보여주는 버퍼 캐시 프로세스를 만든다. 이때, 버퍼 캐시의 해시 큐의 총 크기는 100KB이며, 따라서 가질 수 있는 총 해시 큐의 블록의 수는 25개이다.
따라서 콘솔로 구현 시 필요한 프로세스는 사용자 인터페이스 프로세스와 버퍼 캐시 프로세스 두 개이며, 이 두 프로세스 간의 통신은 각자 자율로 한다. MFC로 구현할 경우는 한 프로젝트 내에서 UI를 구성하여 만들면 되므로, 따로 프로세스를 두 개 만들 필요가 없다.

사용자는 사용자 인터페이스의 파일 생성 메뉴를 통해 충분히 많은 파일을 생성하여 vHDD를 채우고, 이후 파일 읽기 메뉴를 통해 버퍼 캐시를 동작 시킨다.

버퍼 캐시는 사용자가 읽기 메뉴를 통해 전달한 파일을 vHDD에서 읽고, 그것을 (2)번에 쓰여진 처리 방법에 따라 처리한다. 이때, (VII)에 있는 버퍼를 가져오는 5가지 시나리오를 준수하여 처리한다.

버퍼 캐시가 처리되는 과정은 버퍼 캐시 프로세스의 출력창을 통해 실시간으로 보여준다.

프로그램 요구사항

버퍼는 잠김(locked or busy), 잠김 해제(unlocked or free), 지연쓰기(delayed write), 장치로부터 읽고(reading), 쓰는(writing) 상태를 가진다.

커널이 버퍼를 다시 할당하기 전에 이 버퍼의 내용을 디스크에 저장해야 하는데, 이 상태를 지연쓰기(delayed write)라 한다.

장치 번호는 신경 쓰지 않는다.

버퍼의 크기는 25개의 블록을 처리할 수 있을 정도이며, 따라서 해시큐의 크기 역시 같아야 한다.

개발 환경

Platform : Windows

Dev. Language : C/C++(MFC 사용 권장-Console도 무방함)

제출 마감 기한
11월 16일 (금) 23:59 까지

텀 프로젝트 구성 인원
개인 별

제출 방식
소스와 실행 파일, 문서 파일을 압축하여 “Term02_학번_이름”으로 ftp://163.180.116.93 (ID :　os, PW : 1111)에 업로드